package com.zyk.leetcode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @author zhangsan
 * @date 2021/4/18 12:08
 */
public class C102 {

    // https://leetcode-cn.com/problems/binary-tree-level-order-traversal/
    // bfs
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        if (root == null) return ans;
        List<Integer> level = new ArrayList<>();
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        TreeNode cur, end = root, nextEnd = null;
        while (!q.isEmpty()) {
            cur = q.poll();
            level.add(cur.val);
            if (cur.left != null) {
                q.add(cur.left);
                nextEnd = cur.left;
            }
            if (cur.right != null) {
                q.add(cur.right);
                nextEnd = cur.right;
            }
            if (cur == end) {
                end = nextEnd;
                ans.add(level);
                level = new ArrayList<>();
            }
        }
        return ans;
    }


    // dfs
    public List<List<Integer>> levelOrder2(TreeNode root) {
        ans = new ArrayList<>();
        dfs(root, 0);
        return ans;
    }

    List<List<Integer>> ans;

    private void dfs(TreeNode root, int level) {
        if (root == null) return;
        if (level == ans.size()) ans.add(new ArrayList<>());
        ans.get(level).add(root.val);
        dfs(root.left, level+1);
        dfs(root.right, level+1);
    }

}
